1. Field of the Invention
The invention relates to the field of decoding data and in particular, to methods and systems for generating improved speed of lossy data compression decoding such as for image data.
2. Statement of the Problem
In a variety of computing and communication applications, data is encoded and decoded by cooperating elements of a processing or communication system. In computing applications, data may be compressed or encoded for storage and decompressed or decoded for utilization. For example, backup storage of a system may be so compressed (encoded) when stored for archival purposes and decompressed (decoded) when retrieved to restore lost data. Or, for example, image data may be compressed to reduce its required storage space and may be decompressed when presented on a display or document. Similarly, in communication applications, data may be encoded for compression by the transmitter and decompressed by decoding within a receiver.
One common application for such encoding and decoding of data is in digital imaging applications. A digital image may be encoded in a manner that compresses an otherwise significant volume of data for storage and then allows for decoding and decompression when the image is to be presented for further use. The encoding and decoding of images or other data for compression and decompression may also be utilized in communication applications of digital data. The transmitter may encode the image to compress the data and the receiver may utilize corresponding decode capabilities to decompress the data and present it to a user. For example, a computer system may encode (compress) digital image data to be transmitted from the computer system. A printing system may receive the compressed image data and decode (decompress) the received data for presentation on a printed page. Or, for example, a digital image may be encoded for transmission to a personal digital device such as a cell phone or a PDA for display on the LCD screen of the device. The personal digital device would then decode (decompress) the image and display it.
A significant number of digital imaging standards and other data compression/decompression standards have evolved for such applications. For example, JPEG, JPEG 2000, and MPEG are all image encoding/decoding standards that permit significant compression of digital image data. These and other standards include a variety of compression techniques that assure complete fidelity in reproduction of the original image as well as higher levels of compression that do not assure such fidelity in reproducing the original image. Compression techniques that assure such fidelity are often referred to as “lossless” compression whereas compression techniques that do not assure fidelity of the reproduced data are often referred to as “lossy” compression. Because exact reproduction of the original data is not required in a lossy compression scheme, lossy compression typically offers significant improvements in the amount of compression achieved by the encoding/decoding technique. Further, lossy compression techniques may run faster than lossless compression techniques because fidelity in reproduction of the original image is not a requirement.
In a number of such image compression/decompression applications, lossy compression techniques are preferred for their speed and improved compression ratio. For example, some digital images may include more detail than the human eye can recognize and hence lossy compression may produce a decompressed image that is good enough for such an application. Therefore, lossy compression techniques tend to be used where detail of an original image may be lost without defeating the intended purpose of the image transmission and presentation. Further, lossy compression is often used where speed is critical in the compression and decompression processing. Where a device compressing the data and/or decompressing the data has limited processing capability, slow encoding or decoding requiring significant processing capability may be unacceptable.
A number of encoding/decoding standards include features to shift the digital image data into a frequency domain or other domain and then to apply further mathematical techniques to compress the data as shifted into the new domain. For example, JPEG standards include utilization of a discrete cosine transform (“DCT”) image encoding technique coupled with entropy encoding techniques such as Huffman coding of information. The DCT encoding techniques transform the original image data into a frequency domain approximating the image data. Though the transformation into the frequency domain, per se, may not compress the digital image data, it may reveal high frequency changes in the data that may be eliminated as “noise” by further computational transform techniques. Such “noise” may be deemed imperceptible by the human eye or other applications of the data and could thus be eliminated as unimportant. Such elimination of unimportant “noise” may permit significant compression of digital image data. The step of eliminating such noise is often referred to as quantization and represents a scaling of the data such that when restored the noise may be eliminated.
Noise signals so eliminated may be scaled or quantized to zeros in the data as transformed to the frequency domain. Thus, a subsequent step to encode the data as transformed to the frequency domain may compact or compress the encoding of the zero values in the transformed data. This compact encoding of the significant number of zero values in the transformed data allows significant compression of the original data stream.
The computational techniques that perform the requisite mathematics for the transform and quantization are inherently approximations of the actual real number mathematics. These techniques, in particular the quantization step of such a process, essentially discard unimportant data by discarding higher frequency changes in the data that are generally imperceptible in most applications utilizing the digital image. This minimal loss incurred by such DCT or other domain transform encoding techniques, though technically lossy by nature, can render images extremely close to the original digital image.
DCT and other such domain transform encoding techniques (such as wavelets utilized by JPEG 2000) tend to be compute intensive requiring significant mathematical processing power to encode or decode the image data with minimal loss of fidelity. In many practical applications of DCT encoding, the decoder (and sometimes the encoder) impose further loss of fidelity through mathematical shortcuts to speed up the computation process. For example, floating point real number arithmetic (already an approximation of real number arithmetic) may be replaced by faster integer approximation arithmetic. Or, for example, where a particular portion of the approximated image is relatively unchanged, “fastpath” techniques may detect such simple portions of data and dramatically reduce all computation, both floating point or integer approximations thereof. For example, a test may determine that pixels in a particular portion of an image are all the same. The processing for encoding or decoding such a portion may be dramatically reduced by detecting such a condition.
Though such fastpath optimizations are common and may provide significant speed enhancements for certain identified types of data, the more general path of decoding logic is more complicated because of the added testing required to identify the particular fastpath that may be optimized. Typically, such fastpath optimizations are identified for each of several portions of the compressed image. Thus, processing for more general decoding logic paths may be significantly impacted by the added overhead.
In particular, in the DCT encoding standards used in JPEG, a digital image is broken into two dimensional blocks of eight by eight blocks of picture elements. Fastpath techniques are therefore generally applicable to each such block of encoded data. There may be hundreds if not thousands or millions of such blocks in a larger image. The testing for identifying such path fastpath optimizations may therefore impose a significant overhead processing burden on the more general logic cases and paths utilized for many, if not the majority of, other encoded blocks of image where fastpath optimizations may not be applied.
None the less, fastpath improvements address computational overhead associated with DCT algorithm encoding or decoding of individual blocks of the image and are very effective in this regard. The entropy encoding (e.g. Huffman encoding) coupled with the DCT encoding in accordance with the various imaging standards is not generally affected by such fastpath optimizations. As improvements continue to accrue in DCT computational approximations and fastpath optimizations for the DCT encoding, the computational burden associated with the entropy encoding has risen to a larger portion of the total overhead for such image encoding and decoding.
It therefore remains an ongoing problem to further enhance data stream decoding, and in particular image data decoding, in such a manner as to benefit the general logic path for decoding regardless of the number of fastpath optimizations that may be identified for particular DCT encoded blocks of data.